package com.gxc.recursion;

/**
 * 牛牛准备参加学校组织的春游，出发前牛牛准备往背包里装入一些零食，牛牛的背包容量为w。
 * 牛牛家里一共有n袋零食，第i袋零食体积为v[i]。
 * 牛牛想知道在总体积不超过背包容量的情况下，他一共有多少种零食放法(总体积为0也算一种放法)。
 *
 * 解法：
 * 尝试每种零食要和不要。只要总体积不超过背包容量，放法+1,尝试到最后一种零食
 */
public class Backpack2 {

    public static int max(int[] arr, int w) {
        if (w<1 || arr.length==0 || arr==null) return 0;

        return process(arr, w, 0);
    }

    /**
     *
     * @param arr 零食数组
     * @param w  背包剩余体积
     * @param i  零食当前位置
     * @return
     */
    private static int process(int[] arr, int w, int i) {
        if (i==arr.length) return 1;

        int sum = 0;
        //当前位置零食要
        if (w > arr[i]) {
            sum+=process(arr, w - arr[i], i+1);
        }
        //当前位置零食不要
        sum+=process(arr, w, i+1);
        return sum;
    }

    /**
     *
     * @param arr 零食数组
     * @param w  背包剩余体积
     * @param i  零食当前位置
     * @return
     */
    private static int process2(int[] arr, int w, int i) {
        if (i==arr.length) return w>=0?1:0;

        //当前位置零食要
        //当前位置零食不要
        return process2(arr, w, i+1) + process2(arr, w - arr[i], i+1);
    }

    /**
     * 递归转dp
     * @param arr
     * @param w
     * @return
     */
    public static int dp(int[] arr, int w) {
        int[][] dp = new int[w][arr.length+1];

        for (int i = 0; i < dp.length; i++) {
            dp[i][arr.length] = 1;
        }
        for (int j = 0; j < dp[j].length; j++) {
            dp[0][j] = 0;
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = dp[i].length-2; j >=0; j--) {
                dp[i][j] = dp[i][j+1] + (i - arr[j])>=0?dp[i - arr[j]][j+1]:0;
            }
        }

        return dp[w][0];
    }

}
